package com.zhanghp.class03;

import com.zhanghp.refer.ListNode;

/**
 * <h2>
 * 两个链表相加问题
 * </h2>
 * <p>
 * 给定两个<font color="red">非空</font>链表的头节点head1和head2,每个节点只能存储一位数字
 * 认为从左到右是某个数字从低位到高位，返回相加之后的链表
 *  <ul>例子
 *      <li>4 -> 3 -> 6</li>
 *      <li>2 -> 5 -> 3</li>
 *  </ul>
 *  <p>返回     6 -> 8 -> 9</p>
 *  <p>解释     634 + 352 = 986</p>
 *  <hr/>
 * <br/>
 * <p>没参考左神思路，自己写的，超越100%用户，可以优化，左神的代码就很简单，我这个太冗余了</p>
 * <br/>
 * <a href = "https://leetcode.cn/problems/add-two-numbers/submissions/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china">leetcode</a>
 *
 * @author zhanghp
 * @since 2023/10/19 13:41
 */
public class Code05_AddTwoNumbers {
    public static void main(String[] args) {

        addTwoNumbers(null, getl2());
    }

    public static ListNode getl1() {
        return null;
    }

    public static ListNode getl2() {
        ListNode head = new ListNode(9);
        ListNode result = head;
        for (int i = 0; i < 3; i++) {
            head.next = new ListNode(9);
            head = head.next;
        }
        return result;
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            throw new RuntimeException("请转入2个非空链表");
        }
        int carry = 0;
        ListNode result = l2;
        ListNode temp = null;
        while (l1 != null) {
            if (l2 == null) {
                if (temp == null) {
                    result = l1;
                } else {
                    temp.next = l1;
                }
                break;
            }
            int v1 = l1.val;
            int v2 = l2.val;
            int sum = v1 + v2 + carry;
            int newValue = sum % 10;
            carry = sum / 10 == 1 ? 1 : 0;
            l1 = l1.next;
            l2 = l2.next;
            if (temp == null) {
                temp = new ListNode(newValue);
                result = temp;
            } else {
                temp.next = new ListNode(newValue);
                temp = temp.next;
            }
        }
        // 处理长短不一时的逻辑
        while (l1 != null) {
            if (carry != 0) {
                int sum = l1.val + carry;
                int i = sum % 10;
                int i1 = sum / 10;
                l1.val = i;
                carry = i1;
                temp = l1;
                l1 = l1.next;
            } else {
                break;
            }
        }
        while (l2 != null) {
            temp.next = l2;
            if (carry != 0) {
                int sum = l2.val + carry;
                int i = sum % 10;
                int i1 = sum / 10;
                l2.val = i;
                carry = i1;
                temp = l2;
                l2 = l2.next;
            } else {
                break;
            }
        }
        // 进位不为0处理
        if (carry != 0) {
            temp.next = new ListNode(carry);
        }
        return result;
    }
}
